Objects are entities that encapsulate data and, in some environments, operations and methods associated with the object. When an object is created, memory is allocated for the object, and when the object is no longer needed, that memory for the object is deallocated so that the memory can be reused for other purposes. In dynamic run-time environments, objects are allocated and deallocated throughout the life of program, and the memory management of such dynamic objects is crucial to the correctness and performance of dynamic run-time environments.
Many dynamic run-time environments create objects that last as long as the objects are being referenced by a program, and these objects are deallocated when they are no longer referenced through a procedure known as garbage collection. To determine which objects are still referenced and which objects are no longer referenced, many garbage collectors calculate a root set for all the objects such that the transitive closure of objects in the root set (i.e. the set of objects reachable from the object in the root set) contains all the live objects in a memory space. In order to calculate a transitive closure, it is important to determine all the objects that a particular object references. This operation is referred to as scanning the object, which involves visiting every field in the object to determine whether the field contains a reference to another object, and, if the field does indeed contain such a reference, scanning that other object.
In some operating systems or other runtime environments, objects can be discontiguous. These environments, in practice if not by design, limit the guaranteed size of contiguous virtual memory to a “page,” typically about two or four kilobytes in size. This page-size limitation may occur, for example, on computer systems that permit objects to be allocated in a shared memory for access by different processes and even by different processors. If an object is larger than a page or if the object is larger than the available memory on a page, then one part of the object would have to be allocated on one page and part of the object would have to be allocated on another page. The possibility, that objects may be discontiguous, however, greatly complicates the scanning operation, yet for performance reasons it is vital to scan objects as fast as practicable.
Therefore, there is a need for scanning discontiguous objects efficiently for garbage collection.